The present invention relates to memory management in distributed systems, and more particularly, to garbage collection in such systems.
Within conventional computer systems, applications are executed by microprocessors which necessarily use memory locations for storing data and instructions. The contents of memory are changing over time such that, at different times, a memory location is said to be allocated, i.e., used, or unallocated, i.e., unused. More particularly, allocated memory locations are those locations that contain data or instructions that are referenced by other allocated memory locations during normal program execution.
For example, in modern object oriented computing, an xe2x80x9cobjectxe2x80x9d is data that share a particular attribute and occupy a contiguous region of memory. If all objects in a given computer system are permanent, there is no real concern with regard to memory management. That is, the memory space assigned to each object at the start of program execution never changes. However, in most conventional object oriented systems, objects have varying lifetimes that cannot be predicted in advance such that memory locations will transition between allocated and unallocated states. In order to promote the efficient use of memory, unallocated memory locations must be xe2x80x9creclaimedxe2x80x9d so that they may be later allocated as required.
xe2x80x9cGarbagexe2x80x9d is a well-known term in the computer science arts which refers to memory storage locations which contain data that is no longer being used, e.g., in the execution of an application program. xe2x80x9cGarbage collectionxe2x80x9d is another well-known term of art used in describing automatic techniques for identifying garbage and reclaiming those memory locations for future allocation. By automatically identifying accessible, and therefore potentially in-use data, e.g., objects, garbage collection routines shoulder the error-prone task of memory allocation and deallocation for the computer programmer. In freeing computer programmers from such low-level detail, garbage collection at a minimum can improve the quality of program code, increase programmer productivity, and reduce program development costs.
Of course, the many advantages associated with garbage collection are not xe2x80x9cfreexe2x80x9d in terms of computing resources. Traditional garbage collection techniques such as xe2x80x9cstop and copyxe2x80x9d, xe2x80x9cmark and sweepxe2x80x9d and xe2x80x9creference countingxe2x80x9d are described by, for example, Paul R. Wilson, xe2x80x9cUniprocessor Garbage Collection Techniquesxe2x80x9d, In International Workshop on Memory Management, Springer-Verlag, 1992, and Richard Jones et al., Garbage Collection Algorithms for Automatic Dynamic Memory Management, John Wiley and Sons, 1996. The costs associated with such traditional garbage collection techniques manifest themselves, for example, as combinations of increased memory usage, run-time overheads on data accesses, and disruptive latencies in a program""s execution. For example, stop and copy garbage collectors require a substantial amount of additional storage for making copies of live, i.e., allocated, data. This is due to the fact that such collectors periodically copy all reachable objects into a second memory space so the first memory space can be reclaimed in its entirety.
In order to address the inherent costs of garbage collection techniques as described above, the developers of garbage collection routines have incorporated concurrency in their designs whereby garbage collection occurs contemporaneously with application execution. More particularly, concurrent garbage collection techniques fall generally into one of two classes: (1) variations on mark and sweep collectors, see, for example, E. W. Dijkstra et al., xe2x80x9cOn-the-fly garbage collection: An exercise in cooperationxe2x80x9d, Communications of the ACM, 21(11):966-975, November 1978, and G. L. Steele, Jr., xe2x80x9cMultiprocessing compactifying garbage collectionxe2x80x9d, Communications of the ACM, 18(9):495-508, September 1975; and (2) incremental generational collectors, see, for example, H. G. Baker, xe2x80x9cList processing in real time on a serial computerxe2x80x9d, Communications of the ACM, 21(4):280-294, April 1978, A. W. Appel et al., xe2x80x9cReal-time concurrent collection on stock multiprocessorsxe2x80x9d, In Conference on Programming Language Design and Implementation, pp. 11-20, June 1988, and S. Nettles et al., xe2x80x9cReplication-based real-time garbage collectionxe2x80x9d, In Conference on Programming Language Design and Implementation, Association for Computing Machinery, June 1993.
As will be appreciated, the task of defining and implementing garbage collection routines as detailed above using traditional functional programming languages, e.g., C or C++, is ultimately left to the program developer. For example, the emerging use of so-called Java(trademark) bytecodes, particularly in the form of applets, for executing programs via the well-known World Wide Web (xe2x80x9cWWWxe2x80x9d) is one area of tremendous programming growth and technical focus. As is well-known, Java is a popular programming language which enables users to create applications that can be used and executed across the well-known Internet without concerns about platform compatibility or network security. That is, Java is a platform-neutral language which means that programs developed using Java can execute on any computer system without the need for any modifications. Such platform independence stems from the use of a special format for compiled Java programs called xe2x80x9cbytecodesxe2x80x9d which are a set of instructions which look similar to conventional machine code, but are not specific to any one processor. Thus, a Java bytecode can be read and executed by any computer system that has a Java interpreter.
This is in contrast to compilers for non-Java programming languages, e.g., the well-known C programming language, which translate source programs into machine code or processor instructions which are specific to the processor or computer system. In such non-Java systems, if one wants to use the same program on another computer system, the source program must be found and provided as input to the compiler for the different system for recompilation. Thereafter, the recompiled program can be executed on the different computer system. In contrast, to execute a Java program, Java bytecodes are generated by a Java compiler which are executed by a Java interpreter, i.e., a bytecode interpreter, which in turn executes the Java program. Thus, placing the Java program in bytecode form enables the execution of such programs across any platform, operating system, or windowing system so long as the Java interpreter is available. As such, the capability of having a single binary file, i.e., Java bytecode file, executable across multiple platforms is a key attribute which is making Java bytecode, particularly in the form of applets, a common way of executing programs across the World Wide Web.
As will be appreciated, a class file (it will be noted that the terms xe2x80x9cclass file(s)xe2x80x9d and xe2x80x9cbytecode file(s)xe2x80x9d are used interchangeably herein) is typically obtained by compiling a Java file and is a stream of bytes representing a single class in a form suitable for the well-known Java Virtual Machine (xe2x80x9cJVMxe2x80x9d). The Java Virtual Machine executes bytecodes and provides Java with certain fundamental capabilities such as object creation and garbage collection. In particular, Java, as a virtual machine based language, automatically handles all aspects of memory management thereby alleviating the necessity of the programmer having to write specific code modules to perform such tasks, e.g., garbage collection. With regard to garbage collection, because objects are automatically garbage-collected in Java, programmers do not have to (and are barred from) manually freeing memory allocated to an object when use of that object is no longer required by a process. More specifically, the JVM implements parallel garbage collection by executing a separate thread, silently and in the background, dedicated to cleaning up the Java environment of garbage. Essentially, the JVM implements this parallel garbage collection in at least three conventional manners: (1) the JVM examines the current process execution level and if the execution level is relatively xe2x80x9clowxe2x80x9d the JVM spins off the separate garbage collection thread to collect unused memory objects; or (2) the JVM determines that it is close to exhausting all available memory and spins off the separate garbage collection thread to collect unused memory objects; or (3) the program developer can request the JVM to commence garbage collection.
Java""s parallel garbage collection scheme is effective in implementing garbage collection and shielding the memory management operations from the programmer in almost all applications. However, in certain time-critical, real-time distributed applications Java""s garbage collection operations severely impacts its use in such applications (e.g., telephony communication systems) due to certain processing delays. More particularly, in accordance with Java""s conventional garbage collection procedures, the garbage collection process consumes a significant amount of processor time, i.e., CPU cycles, and locks certain memory regions thereby preventing other currently running threads in the same JVM from executing. As such, the garbage collection process introduces certain non-deterministic processing delays into the currently executing threads in the JVM. Such delays severely impact time-critical, real-time applications which impose stringent timing requirements for application processing.
Therefore, a need exists for a system implementing garbage collection on virtual machines which does not negatively impact the execution of time-constrained processes.
An aspect of the present invention is directed to a system for executing distributed processes on garbage collecting virtual machines. More particularly, garbage collection is delivered to distributed processes, i.e., applications, such that the garbage collection process does not run concurrently with real-time processing.
In accordance with the preferred embodiment of the invention, a distributed architecture is defined that employs a collection of resources each of which exposes a hierarchical namespace executing on garbage collecting virtual machines. The architecture of the preferred embodiment is directed to providing telephony services and includes two fundamental resource types, namely, i) the device server and ii) the call coordinator, which are interconnected by a network employing a common protocol, e.g., transmission control protocol/Internet protocol (xe2x80x9cTCP/IPxe2x80x9d). Each resource can participate in more than one call, i.e., each resource acts as a distributed file system that can arbitrate various requests presented to it. The interaction between the various resources that are available, which are substantially independent, follows conventional xe2x80x9cclient-serverxe2x80x9d architecture principles to implement end-to-end communication.
More particularly, a call coordinator functions in the role of the xe2x80x9cclientxe2x80x9d of the conventional xe2x80x9cclient-serverxe2x80x9d architecture, e.g., it initiates requests for services to the various device servers. Since the call coordinator is the client, it is able to request service from various ones of the servers, i.e., device servers or gateway servers, as is appropriate for the service being provided on a particular call. The device servers are unaware of so-called communication state, which is the interaction among multiple device servers. Instead, communication state is maintained by the call coordinator, which exposes the communication state as a hierarchical namespace. A hierarchical namespace is analogous to a computer disk-based hierarchical file system except that what appears in the nodes and leaves of the hierarchy may not be actual directories and files but instead may be other data structures in memory which are presented in the form of a file system. In addition, the call coordinator treats the processing of a call as a sequence of steps each of which can be implemented by a small piece of computer executable code called a xe2x80x9cfeature appletxe2x80x9d.
More specifically, typical device servers represent physical/logical telephone devices, which include end-point device servers and gateway device servers. End-point device servers represent controls for communication, such as keypads, indicator lamps, and displays, and perform media rendering, e.g., voice digitization, transport, and reconstruction. End-point device servers may include phone device servers. Gateway device servers have two so-called xe2x80x9csidesxe2x80x9d. One side is implemented to appear to a call coordinator as if it were a device server, and the other side has an interface adapted to interwork with a preexisting island of telephone service. Gateway device servers may include line device servers. In the term xe2x80x9cdevice serverxe2x80x9d, xe2x80x9cserverxe2x80x9d is used in the conventional manner of the xe2x80x9cclient-serverxe2x80x9d architecture, where the server processes requests from the clients and does not take action unless it is in response to a client request.
In accordance with the principles of the invention, garbage collection is provided such that n call coordinators can simultaneously process k calls thereby yielding an effective call processing capacity of (nxc3x97k) calls. In accordance with an aspect of the invention, a group of at least two call coordinators are deployed in a load share mode. That is, in accordance with the preferred embodiment, the device servers send call requests to any of the active call coordinators as decided by the call coordinators in the group (i.e., the active status of any particular call coordinator is decided by the call coordinator group). Further, when any particular call coordinator reaches a certain threshold, TI, that call coordinator enters into a so-called xe2x80x9chibernationxe2x80x9d state. TI is a measure of total call processing time allocable to the call coordinator before garbage collection is required. A hibernating call coordinator indicates to the device servers that its current status is inactive. The device servers thereby refrain from using that particular call coordinator until further notice and choose an available active call coordinator from the call coordinator group for routing new call requests. The call coordinator which has entered into hibernation initiates garbage collection and after completing the garbage collection cycle indicates to the device servers that it can now begin to receive new call processing requests. As such, the call coordinator is now marked active by the device servers.
In accordance with an aspect of the invention, garbage collection on the virtual machine is governed, at a minimum, by TI (i.e., the measure of total call processing time allocable to the call coordinator before garbage collection is required), process hibernation time, TH, and the total garbage collection time required for a process, TGCI. More particularly, in accordance with the preferred embodiment invention, garbage collection on the virtual machine occurs in accordance with the relationship: (nxe2x88x921) TI greater than TH+TGCI, where n is the total number of call coordinators. Significantly, we have recognized that through the empirical derivation of TI, TH, and TGCI, garbage collection is delivered on the virtual machine with no significant processing impact on the currently executing processes.
Advantageously, in accordance with the invention, distributed application programs are executed on garbage collecting virtual machines without any adverse processing impact resulting from garbage collection.